/*
https://leetcode.cn/problems/maximum-number-of-non-overlapping-substrings/solution/zui-duo-de-bu-zhong-die-zi-zi-fu-chuan-by-leetcode/
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1520 {
    public List<String> maxNumOfSubstrings(String s) {
        int[] first=new int[26];
        int[] last=new int[26];
        Arrays.fill(first,-1);
        for (int i=0;i<s.length();i++){
            if (first[s.charAt(i)-'a']==-1){
                first[s.charAt(i)-'a']=i;
            }
            last[s.charAt(i)-'a']=i;
        }
        List<int[]> list=new ArrayList<>();
        for (int i=0;i<26;i++){
            if (first[i]!=-1){
                for (int j=first[i];j<=last[i];j++){
                    int c=s.charAt(j)-'a';
                    if (first[i]<=first[c] && last[i]>=last[c]){
                        continue;
                    }
                    first[i]=Math.min(first[i],first[c]);
                    last[i]=Math.max(last[i],last[c]);
                    j=first[i];
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (first[i]!=-1){
                list.add(new int[]{first[i],last[i]});
            }
        }
        list.sort((a,b)->a[1]==b[1]?(a[1]-a[0]-b[1]+b[0]):a[1]-b[1]);
        List<int[]> ans=new ArrayList<>();
        ans.add(list.get(0));
        int p=list.get(0)[1];
        for (int i=1;i<list.size();i++){
            if (list.get(i)[0]>p){
                ans.add(list.get(i));
                p=list.get(i)[1];
            }
        }
        List<String> r=new ArrayList<>();
        for (int[] an : ans) {
            r.add(s.substring(an[0],an[1]+1));
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1520().maxNumOfSubstrings("adefaddaccc"));
    }
}
